Min Max Occlusion Volumes
Introduction
My modem has been rather max'd out recently from reading most 3d related articles I could find on the net. I've looked at clipping, culling, curves, engines, intersections, lighting, occlusion, partitioning methods, portals, rendering, scene traversal methods, shadows, terrains, transformation and visibility (phew!). The field of 3d computer graphics is a complex but highly interesting one because there is still no clear, 'optimum' way.
In this article I want to talk about a rather simple (and crude) idea for quickly determining object occlusion. I haven't seen this method mentioned anywhere, so here goes...
What is Occlusion?
If you're familiar with 3d graphics but haven't heard of 'occlusion' then don't worry, it's just a fancy name for "Not drawing items which are totally behind other items". In most cases 'items' mean the same as polygons.
A simple example of this would be a line of dominos all standing on their edges. If you looked directly at the first domino then ALL of the others would be totally obscured by the front one. You would only need to render a single domino. All the ones behind it can be ignored.
The problem
Many of algorithms on the net deal with the occlusion problem by casting a 'beam' from the eye-point to each polygon. This beam is like the expanding light from a torch. I won't go into the details here because there's plenty of good information on the net. For each and every polygon a beam is calculated and inserted into a 'beam-tree' structure. The structure is used to determine if future polygons are totally occluded behind previous ones.
Like most 3d-pipeline tasks we don't want to check each and every polygon. It would be nice to perform occlusion operations on an object-by-object basis. To create a beam we ideally need a flat 2d polygon but that would mean projecting an entire object's worth of polygons just to obtain the silhouette edges. That's far too expensive in terms of CPU.
So we need to greatly simplify the object to something that doesn't need the projection calculations. Something that is totally independent of view angle would be an additional bonus.
Describing the object
The simplest method of describing a complex 3d object is a bounding-volume (either a box or a sphere if you wish). A pre-processing step can generate the bounding volume and store it along with each 3d object.
"Ah", you might be thinking, "I can use the bounding volumes for occlusion!"
The Min and Max volumes
But in fact you need two such volumes. One is the 'max' bounding volume (which surrounds the entire object) and one is the 'min' bounding volume (which is the smallest volume in the centre of the object). The whole idea of the 'min' volume is that it describes the minimum coverage of the object and likewise the 'max' volume is the maximum coverage area.
Once we've got the min and max volumes the occlusion can be done with nothing more complex than a rectangle overlap test. We take the min volume of the occluder (the nearest object) and test it against the max volume of the occludee (the far object).
If (( far.max.left >= near.min.left) &&
( far.max.right <= near.min.right) &&
( far.max.top >= near.min.top) &&
( far.max.bottom <= near.min.bottom)
) ... object is totally occluded !! ....
Of course each volume needs to be scaled depending on it's distance from the eye-point (further away objects are smaller :)
Improvement
At it stands the above min max volume method performs very badly for objects that are long and thin because the min volume would be very small and the max volume very large. Ideally we want objects whose 'range' (max volume - min volume) is very low and whose min, max values change as the object rotates in relation to our viewpoint.
We can't really solve the range problem easily because we want to allow objects of any shape. If we only used spheres then the 'range' of every object would be 0. The occlusion testing of spheres is extremely simple and takes the form of overlapping circle checks. But we can tackle the dynamic volumes which change depending on our viewpoint by transforming (rotating and scaling) two (x,y,z) points from our object and using them to define our min and max volumes. This way as the object and/or our view angle to it changes our min, max volumes more closely follows it. In the case of a long, thin object like a kitchen knife it has more chance of it being totally hidden by another object when it is pointing directly towards us or away from us.
The min, max volume value (and the range) are cheap to calculate but could be used to classify the occlusion and help speed up the entire process. For example the min volume is a good indication of how good/bad an occluder the object is (the bigger the min volume, the better the chances of it totally hiding other objects). If the min volume value is small then the object is more likely to be hidden by another object.
Also the min, max volume values could be used to calculate a rough 'scene complexity' value so we can adjust the level-of-detail depending on how many polygons we 'estimate' that need to be drawn. Most of the LOD documents I've seen only employ techniques like mesh-simplification depending on the distance the object is from the viewpoint (i.e. the Z value) but LOD can also be used when a scene is highly complex and filled with thousands of small objects. We adjust the LOD to help maintain a near-constant frame rate.
Future work
Of course the above idea is still very crude and depending on each object's shape the results will vary greatly. A proper beam-tree method will give much greater accuracy, but this method is intended to be a first step in rejecting totally occluded objects (instead of polygons) without a vast deal of processing time. The rectangle (or whatever volume you wish to use) can easily be sub-divided and stored in a tree structure (just like your normal oct-trees or kD-trees).
If you are using portals or some other geometry that is quick to test objects against walls/surfaces then it should be possible to develop this method further and occlude objects that are totally behind walls/surfaces using nothing more complex than overlapping rectangle (or circle) tests.
Well, I hope someone found this idea interesting. It wasn't very ground breaking but it might inspire someone else to improve it, until then, may your pipeline never stall and your cache never miss :)
Regards